#ifndef	__BFX_HASHSET_H__
#define	__BFX_HASHSET_H__

#include "HashTraits.h"

namespace BFX
{
// Represents a hash set of values.
template<class TYPE, class HashTraits = HashTraits<TYPE> >
class BFX_TMPL HashSet
{
public:
	// Inner types.
	typedef	const TYPE&	ARG_TYPE;
	typedef struct Entry
	{
		TYPE	value;
	protected:
		Entry(ARG_TYPE newValue) : value(newValue)
		{}
	}*POSITION;

protected:
	class Assoc : public Entry
	{
		friend class HashSet;
		Assoc*	pNext;			// pointer to next association.
		int		nHashValue;
		const HashSet*	pContainer;
	public:
		Assoc(ARG_TYPE newValue)
			: Entry(newValue), pNext(NULL), nHashValue(0), pContainer(NULL)
		{
		}
	};

public:
	// Initializes a new instance of the HashSet class.
	HashSet()
	{
		m_pHashSet = NULL;
		m_nHashSetSize = 16;
		m_nCount = 0;
	}
	virtual ~HashSet()
	{
		Clear();
		BFX_ASSERT(m_nCount == 0);
	}

	// Adds the specified element to a set.
	// Returns true if the element is added, false if the element is already present.
	bool Add(ARG_TYPE newValue)
	{
		int nHashValue, nHashBucket;
		Assoc* pAssoc;

		// test if exists.
		if ((pAssoc = GetAssocAt(newValue, nHashBucket, nHashValue)) != NULL)
			return false;

		if (m_pHashSet == NULL)
			Init();
		BFX_ASSERT(m_pHashSet);
		// it doesn't exist, add a new Association
		pAssoc = NewAssoc(newValue, nHashValue);

		// put into hash set
		pAssoc->pNext = m_pHashSet[nHashBucket];
		m_pHashSet[nHashBucket] = pAssoc;

		return true;
	}
	// Removes the specified element from a set.
	// Returns true if the element is successfully found and removed, false if item is not found.
	bool Remove(ARG_TYPE value)
	{
		if (m_pHashSet == NULL)
			return false;  // nothing in the set

		int nHashValue = HashTraits::GetHashCode(value);
		Assoc** ppAssocPrev = &m_pHashSet[nHashValue % m_nHashSetSize];

		Assoc* pAssoc;
		for (pAssoc = *ppAssocPrev; pAssoc != NULL; pAssoc = pAssoc->pNext)
		{
			if ((pAssoc->nHashValue == nHashValue) && HashTraits::Equals(pAssoc->value, value))
			{
				// remove it
				*ppAssocPrev = pAssoc->pNext;  // remove from list
				FreeAssoc(pAssoc);
				return true;
			}
			ppAssocPrev = &pAssoc->pNext;
		}
		return false;  // not found
	}
	// Removes all elements from the set.
	void Clear()
	{
		if (m_pHashSet != NULL)
		{
			// destroy elements
			for (UINT nHash = 0; nHash < m_nHashSetSize; nHash++)
			{
				Assoc* pAssoc, *pNext;
				for (pAssoc = m_pHashSet[nHash]; pAssoc != NULL;
					pAssoc = pNext)
				{
					pNext = pAssoc->pNext;
					delete pAssoc;
				}
			}

			// free hash set
			delete[] m_pHashSet;
			m_pHashSet = NULL;
		}
		m_nCount = 0;
	}
	// Determines whether a set contains the specified element.
	// Returns true if the set contains the specified element, otherwise false.
	bool Contains(ARG_TYPE value) const
	{
		int nHashValue, nHashBucket;
		Assoc* pAssoc = GetAssocAt(value, nHashBucket, nHashValue);

		return pAssoc == NULL ? false : true;
	}

	// Gets number of elements.
	int GetSize() const
	{
		return m_nCount;
	}

	//
	// Iteration methods
	//

	// Searches the set to find the entry matching the specified value
	// Returns NULL if not found.
	POSITION LookupEntry(ARG_TYPE value) const
	{
		int nHashValue, nHashBucket;
		Assoc* pAssoc = GetAssocAt(value, nHashBucket, nHashValue);

		return pAssoc;
	}
	// Gets the first entry of the set.
	// Returns NULL if the set is empty.
	POSITION GetFirstEntry() const
	{
		Assoc* pAssocRet = NULL;
		if (m_pHashSet != NULL)
		{
			for (UINT nBucket = 0; nBucket < m_nHashSetSize; nBucket++)
			{
				if ((pAssocRet = m_pHashSet[nBucket]) != NULL)
				{
					break;
				}
			}
		}

		return pAssocRet;
	}
	// Gets the last entry of the set.
	// Returns NULL if the set is empty.
	POSITION GetLastEntry() const
	{
		Assoc* pAssocRet = NULL;
		if (m_pHashSet)
		{
			for (UINT nBucket = (m_nHashSetSize - 1); nBucket >= 0; nBucket--)
			{
				for (pAssocRet = m_pHashSet[nBucket]; ; pAssocRet = pAssocRet->pNext)
				{
					if (pAssocRet == NULL || pAssocRet->pNext == NULL)
						break;
				}
				if (pAssocRet != NULL)
					break;
			}
		}

		return pAssocRet;
	}
	// Gets the next entry.
	// Returns NULL if the given entry at the last position.
	POSITION GetNextEntry(POSITION pEntry) const
	{
		BFX_ASSERT(m_pHashSet);  // never call on empty map
		BFX_ASSERT(pEntry);

		Assoc* pAssoc = (Assoc*)pEntry;
		BFX_ASSERT(pAssoc->pContainer == this);
		Assoc* pAssocNext = NULL;
		if ((pAssocNext = pAssoc->pNext) == NULL)
		{
			// go to next bucket
			for (UINT nBucket = (pAssoc->nHashValue % m_nHashSetSize) + 1;
				nBucket < m_nHashSetSize; nBucket++)
				if ((pAssocNext = m_pHashSet[nBucket]) != NULL)
					break;
		}

		return pAssocNext;
	}
	// Gets the previous entry.
	// Returns NULL if the given entry at the first position.
	POSITION GetPrevEntry(POSITION pEntry) const
	{
		BFX_ASSERT(m_pHashSet);  // never call on empty map
		BFX_ASSERT(pEntry);

		Assoc* pAssoc = (Assoc*)pEntry;
		BFX_ASSERT(pAssoc->pContainer == this);
		Assoc* pAssocPrev = NULL;
		for (int nBucket = (pAssoc->nHashValue % m_nHashSetSize); nBucket >= 0; nBucket--)
		{
			pAssocPrev = m_pHashSet[nBucket];
			if (pAssocPrev == NULL || pAssocPrev == pAssoc)
				continue;
			for (;;)
			{
				if (pAssocPrev->pNext == pAssoc || pAssocPrev->pNext == NULL)
					break;
				pAssocPrev = pAssocPrev->pNext;
			}
			break;
		}

		return pAssocPrev;
	}

	//
	// Helper methods
	//

	// Creates an array from the set.
	Array<TYPE> ToArray() const
	{
		Array<TYPE> results(m_nCount);
		for (POSITION entry = GetFirstEntry(); entry != NULL; entry = GetNextEntry(entry))
		{
			results.Add(entry->value);
		}
		return results;
	}

private:
	void Init()
	{
		// Used to force allocation of a hash set or to override the default
		//   hash set size of (which is fairly small)
		BFX_ASSERT(m_nCount == 0);

		if (m_pHashSet != NULL)
		{
			// free hash set
			delete[] m_pHashSet;
			m_pHashSet = NULL;
		}

		m_pHashSet = new Assoc* [m_nHashSetSize];
		BFX_ASSERT(m_pHashSet);
		memset(m_pHashSet, 0, sizeof(Assoc*) * m_nHashSetSize);
	}
	Assoc* NewAssoc(ARG_TYPE value, int nHashValue)
	{
		// NOTE: we can use object pool instead new operation directly.
		Assoc* pAssoc = new Assoc(value);
		pAssoc->nHashValue = nHashValue;
		pAssoc->pContainer = this;
		m_nCount++;
		return pAssoc;
	}
	void FreeAssoc(Assoc* pAssoc)
	{
		// NOTE: we can use object pool instead delete operation directly.
		delete pAssoc;
		m_nCount--;
		BFX_ASSERT(m_nCount >= 0);  // make sure we don't underflow

		// if no more elements, cleanup completely
		if (m_nCount == 0)
			Clear();
	}
	Assoc* GetAssocAt(ARG_TYPE value, int& nHashBucket, int& nHashValue) const
	{
		nHashValue = HashTraits::GetHashCode(value);
		nHashBucket = (UINT32)nHashValue % m_nHashSetSize;

		Assoc* pAssoc = NULL;
		if (m_pHashSet != NULL)
		{
			for (pAssoc = m_pHashSet[nHashBucket]; pAssoc != NULL; pAssoc = pAssoc->pNext)
			{
				if (pAssoc->nHashValue == nHashValue && HashTraits::Equals(pAssoc->value, value))
					return pAssoc;
			}
		}
		return pAssoc;
	}

private:
	Assoc** m_pHashSet;
	UINT m_nHashSetSize;
	int m_nCount;
};

}	//	namespace BFX

#endif	//	__BFX_HASHSET_H__
